package personal.leil.learning.merge;

import personal.leil.learning.utils.ArrayUtils;

/**
 * 归并排序
 * <p>
 * 归并排序代码实现
 * </p>
 *
 * @author Leil
 * @version 1.0
 * @since 2024-1-2
 */
public class MergeSort {

    public static void mergeSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        process(arr, 0, arr.length - 1);
    }

    /**
     * 归并排序
     * <p>
     * ①将数组分为左右两部分
     * ②左右两部分分别递归的进行归并操作
     * ③每次递归后对处理部分进行归并操作，并将归并后的结果赋值给源数组
     * </p>
     *
     * @param arr source array
     * @param L   left bound index for recursion
     * @param R   right bound index for recursion
     */
    public static void process(int[] arr, int L, int R) {
        if (L == R) {
            return;
        }
        int M = L + ((R - L) >> 1);
        process(arr, L, M);
        process(arr, M + 1, R);
        int[] help = merge(arr, L, M, M + 1, R);
        for (int i = 0; i < help.length; i++) {
            int index = L + i;
            arr[index] = help[i];
        }
    }

    /**
     * 归并
     * <p>
     * ①开辟一个足以归并数组两部分的辅助数组
     * ②当第一部分和第二部分都不越界的时候，将小的先复制到辅助数组
     * ③直到一部分越界，将另一部分全部复制到辅助数组
     * </p>
     *
     * @param arr source array
     * @param l1  left bound index of left array range
     * @param r1  right bound index of left array range
     * @param l2  left bound index of right array range
     * @param r2  right bound index of right array range
     * @return new array after merge
     */
    public static int[] merge(int[] arr, int l1, int r1, int l2, int r2) {
        int len = (r1 - l1 + 1) + (r2 - l2 + 1);
        int[] help = new int[len];
        int i = 0;
        while (l1 <= r1 && l2 <= r2) {
            help[i++] = arr[l1] > arr[l2] ? arr[l2++] : arr[l1++];
        }
        while (l1 <= r1) {
            help[i++] = arr[l1++];
        }
        while (l2 <= r2) {
            help[i++] = arr[l2++];
        }
        return help;
    }

    /********************* For Test *************************/

    public static void main(String[] args) {
        int[] arr = ArrayUtils.generateRandomArr(20);
        System.out.println("before sort:");
        ArrayUtils.printArr(arr);
        mergeSort(arr);
        System.out.println("after sort:");
        ArrayUtils.printArr(arr);
    }
}
